home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / opo.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  15.9 KB  |  616 lines  |  [TEXT/R*ch]
  1. #include "espresso.h"
  2.  
  3. /*
  4.  *   Phase assignment technique (T. Sasao):
  5.  *
  6.  *      1. create a function with 2*m outputs which implements the
  7.  *      original function and its complement for each output
  8.  *
  9.  *      2. minimize this function
  10.  *
  11.  *      3. choose the minimum number of prime implicants from the
  12.  *      result of step 2 which are needed to realize either a function
  13.  *      or its complement for each output
  14.  *
  15.  *  Step 3 is performed in a rather crude way -- by simply multiplying
  16.  *  out a large expression of the form:
  17.  *
  18.  *      I = (ab + cdef)(acd + bgh) ...
  19.  *
  20.  *  which is a product of m expressions where each expression has two
  21.  *  product terms -- one representing which primes are needed for the
  22.  *  function, and one representing which primes are needed for the
  23.  *  complement.  The largest product term resulting shows which primes
  24.  *  to keep to implement one function or the other for each output.
  25.  *  For problems with many outputs, this may grind to a
  26.  *  halt.
  27.  *
  28.  *  Untried: form complement of I and use unate_complement ...
  29.  *
  30.  *  I have unsuccessfully tried several modifications to the basic
  31.  *  algorithm.  The first is quite simple: use Sasao's technique, but
  32.  *  only commit to a single output at a time (rather than all
  33.  *  outputs).  The goal would be that the later minimizations can "take
  34.  *  into account" the partial assignment at each step.  This is
  35.  *  expensive (m+1 minimizations rather than 2), and the results are
  36.  *  discouraging.
  37.  *
  38.  *  The second modification is rather complicated.  The result from the
  39.  *  minimization in step 2 is guaranteed to be minimal.  Hence, for
  40.  *  each output, the set of primes with a 1 in that output are both
  41.  *  necessary and sufficient to implement the function.  Espresso
  42.  *  achieves the minimality using the routine MAKE_SPARSE.  The
  43.  *  modification is to prevent MAKE_SPARSE from running.  Hence, there
  44.  *  are potentially many subsets of the set of primes with a 1 in a
  45.  *  column which can be used to implement that output.  We use
  46.  *  IRREDUNDANT to enumerate all possible subsets and then proceed as
  47.  *  before.
  48.  */
  49.  
  50. static int opo_no_make_sparse;
  51. static int opo_repeated;
  52. static int opo_exact;
  53. void minimize();
  54.  
  55. void phase_assignment(PLA, opo_strategy)
  56. pPLA PLA;
  57. int opo_strategy;
  58. {
  59.     opo_no_make_sparse = opo_strategy % 2;
  60.     skip_make_sparse = opo_no_make_sparse;
  61.     opo_repeated = (opo_strategy / 2) % 2;
  62.     opo_exact = (opo_strategy / 4) % 2;
  63.  
  64.     /* Determine a phase assignment */
  65.     if (PLA->phase != NULL) {
  66.     FREE(PLA->phase);
  67.     }
  68.  
  69.     if (opo_repeated) {
  70.     PLA->phase = set_save(cube.fullset);
  71.     repeated_phase_assignment(PLA);
  72.     } else {
  73.     PLA->phase = find_phase(PLA, 0, (pcube) NULL);
  74.     }
  75.  
  76.     /* Now minimize with this assignment */
  77.     skip_make_sparse = FALSE;
  78.     (void) set_phase(PLA);
  79.     minimize(PLA);
  80. }
  81.  
  82. /*
  83.  *  repeated_phase_assignment -- an alternate strategy which commits
  84.  *  to a single phase assignment a step at a time.  Performs m + 1
  85.  *  minimizations !
  86.  */
  87. void repeated_phase_assignment(PLA)
  88. pPLA PLA;
  89. {
  90.     int i;
  91.     pcube phase;
  92.  
  93.     for(i = 0; i < cube.part_size[cube.output]; i++) {
  94.  
  95.     /* Find best assignment for all undecided outputs */
  96.     phase = find_phase(PLA, i, PLA->phase);
  97.  
  98.     /* Commit for only a single output ... */
  99.     if (! is_in_set(phase, cube.first_part[cube.output] + i)) {
  100.         set_remove(PLA->phase, cube.first_part[cube.output] + i);
  101.     }
  102.  
  103.     if (trace || summary) {
  104.         printf("\nOPO loop for output #%d\n", i);
  105.         printf("PLA->phase is %s\n", pc1(PLA->phase));
  106.         printf("phase      is %s\n", pc1(phase));
  107.     }
  108.     set_free(phase);
  109.     }
  110. }
  111.  
  112.  
  113. /*
  114.  *  find_phase -- find a phase assignment for the PLA for all outputs starting
  115.  *  with output number first_output.
  116.  */
  117. pcube find_phase(PLA, first_output, phase1)
  118. pPLA PLA;
  119. int first_output;
  120. pcube phase1;
  121. {
  122.     pcube phase;
  123.     pPLA PLA1;
  124.  
  125.     phase = set_save(cube.fullset);
  126.  
  127.     /* setup the double-phase characteristic function, resize the cube */
  128.     PLA1 = new_PLA();
  129.     PLA1->F = sf_save(PLA->F);
  130.     PLA1->R = sf_save(PLA->R);
  131.     PLA1->D = sf_save(PLA->D);
  132.     if (phase1 != NULL) {
  133.     PLA1->phase = set_save(phase1);
  134.     (void) set_phase(PLA1);
  135.     }
  136.     EXEC_S(output_phase_setup(PLA1, first_output), "OPO-SETUP ", PLA1->F);
  137.  
  138.     /* minimize the double-phase function */
  139.     minimize(PLA1);
  140.  
  141.     /* set the proper phases according to what gives a minimum solution */
  142.     EXEC_S(PLA1->F = opo(phase, PLA1->F, PLA1->D, PLA1->R, first_output),
  143.         "OPO       ", PLA1->F);
  144.     free_PLA(PLA1);
  145.  
  146.     /* set the cube structure to reflect the old size */
  147.     setdown_cube();
  148.     cube.part_size[cube.output] -=
  149.     (cube.part_size[cube.output] - first_output) / 2;
  150.     cube_setup();
  151.  
  152.     return phase;
  153. }
  154.  
  155. /*
  156.  *  opo -- multiply the expression out to determine a minimum subset of
  157.  *  primes.
  158.  */
  159.  
  160. /*ARGSUSED*/
  161. pcover opo(phase, T, D, R, first_output)
  162. pcube phase;
  163. pcover T, D, R;
  164. int first_output;
  165. {
  166.     int offset, output, i, last_output, ind;
  167.     pset pdest, select, p, p1, last, last1, not_covered, tmp;
  168.     pset_family temp, T1, T2;
  169.  
  170.     /* must select all primes for outputs [0 .. first_output-1] */
  171.     select = set_full(T->count);
  172.     for(output = 0; output < first_output; output++) {
  173.     ind = cube.first_part[cube.output] + output;
  174.     foreachi_set(T, i, p) {
  175.         if (is_in_set(p, ind)) {
  176.         set_remove(select, i);
  177.         }
  178.     }
  179.     }
  180.  
  181.     /* Recursively perform the intersections */
  182.     offset = (cube.part_size[cube.output] - first_output) / 2;
  183.     last_output = first_output + offset - 1;
  184.     temp = opo_recur(T, D, select, offset, first_output, last_output);
  185.  
  186.     /* largest set is on top -- select primes which are inferred from it */
  187.     pdest = temp->data;
  188.     T1 = new_cover(T->count);
  189.     foreachi_set(T, i, p) {
  190.     if (! is_in_set(pdest, i)) {
  191.         T1 = sf_addset(T1, p);
  192.     }
  193.     }
  194.  
  195.     set_free(select);
  196.     sf_free(temp);
  197.  
  198.     /* finding phases is difficult -- see which functions are not covered */
  199.     T2 = complement(cube1list(T1));
  200.     not_covered = new_cube();
  201.     tmp = new_cube();
  202.     foreach_set(T, last, p) {
  203.     foreach_set(T2, last1, p1) {
  204.         if (cdist0(p, p1)) {
  205.         (void) set_or(not_covered, not_covered, set_and(tmp, p, p1));
  206.         }
  207.     }
  208.     }
  209.     free_cover(T);
  210.     free_cover(T2);
  211.     set_free(tmp);
  212.  
  213.     /* Now reflect the phase choice in a single cube */
  214.     for(output = first_output; output <= last_output; output++) {
  215.     ind = cube.first_part[cube.output] + output;
  216.     if (is_in_set(not_covered, ind)) {
  217.         if (is_in_set(not_covered, ind + offset)) {
  218.         fatal("error in output phase assignment");
  219.         } else {
  220.         set_remove(phase, ind);
  221.         }
  222.     }
  223.     }
  224.     set_free(not_covered);
  225.     return T1;
  226. }
  227.  
  228. pset_family opo_recur(T, D, select, offset, first, last)
  229. pcover T, D;
  230. pcube select;
  231. int offset, first, last;
  232. {
  233.     static int level = 0;
  234.     int middle;
  235.     pset_family sl, sr, temp;
  236.  
  237.     level++;
  238.     if (first == last) {
  239. #if 0
  240.     if (opo_no_make_sparse) {
  241.         temp = form_cover_table(T, D, select, first, first + offset);
  242.     } else {
  243.         temp = opo_leaf(T, select, first, first + offset);
  244.     }
  245. #else
  246.     temp = opo_leaf(T, select, first, first + offset);
  247. #endif
  248.     } else {
  249.     middle = (first + last) / 2;
  250.     sl = opo_recur(T, D, select, offset, first, middle);
  251.     sr = opo_recur(T, D, select, offset, middle+1, last);
  252.     temp = unate_intersect(sl, sr, level == 1);
  253.     if (trace) {
  254.         printf("# OPO[%d]: %4d = %4d x %4d, time = %s\n", level - 1,
  255.         temp->count, sl->count, sr->count, print_time(ptime()));
  256.         (void) fflush(stdout);
  257.     }
  258.     free_cover(sl);
  259.     free_cover(sr);
  260.     }
  261.     level--;
  262.     return temp;
  263. }
  264.  
  265.  
  266. pset_family opo_leaf(T, select, out1, out2)
  267. register pcover T;
  268. pset select;
  269. int out1, out2;
  270. {
  271.     register pset_family temp;
  272.     register pset p, pdest;
  273.     register int i;
  274.  
  275.     out1 += cube.first_part[cube.output];
  276.     out2 += cube.first_part[cube.output];
  277.  
  278.     /* Allocate space for the result */
  279.     temp = sf_new(2, T->count);
  280.  
  281.     /* Find which primes are needed for the ON-set of this fct */
  282.     pdest = GETSET(temp, temp->count++);
  283.     (void) set_copy(pdest, select);
  284.     foreachi_set(T, i, p) {
  285.     if (is_in_set(p, out1)) {
  286.         set_remove(pdest, i);
  287.     }
  288.     }
  289.  
  290.     /* Find which primes are needed for the OFF-set of this fct */
  291.     pdest = GETSET(temp, temp->count++);
  292.     (void) set_copy(pdest, select);
  293.     foreachi_set(T, i, p) {
  294.     if (is_in_set(p, out2)) {
  295.         set_remove(pdest, i);
  296.     }
  297.     }
  298.  
  299.     return temp;
  300. }
  301.  
  302. #if 0
  303. pset_family form_cover_table(F, D, select, f, fbar)
  304. pcover F, D;
  305. pset select;
  306. int f, fbar;        /* indices of f and fbar in the output part */
  307. {
  308.     register int i;
  309.     register pcube p;
  310.     pset_family f_table, fbar_table;
  311.  
  312.     /* setup required for fcube_is_covered */
  313.     Rp_size = F->count;
  314.     Rp_start = set_new(Rp_size);
  315.     foreachi_set(F, i, p) {
  316.     PUTSIZE(p, i);
  317.     }
  318.     foreachi_set(D, i, p) {
  319.     RESET(p, REDUND);
  320.     }
  321.  
  322.     f_table = find_covers(F, D, select, f);
  323.     fbar_table = find_covers(F, D, select, fbar);
  324.     f_table = sf_append(f_table, fbar_table);
  325.  
  326.     set_free(Rp_start);
  327.     return f_table;
  328. }
  329.  
  330.  
  331. pset_family find_covers(F, D, select, n)
  332. pcover F, D;
  333. register pset select;
  334. int n;
  335. {
  336.     register pset p, last, new;
  337.     pcover F1;
  338.     pcube *Flist;
  339.     pset_family f_table, table;
  340.     int i;
  341.  
  342.     n += cube.first_part[cube.output];
  343.  
  344.     /* save cubes in this output, and remove the output variable */
  345.     F1 = new_cover(F->count);
  346.     foreach_set(F, last, p)
  347.     if (is_in_set(p, n)) {
  348.         new = GETSET(F1, F1->count++);
  349.         set_or(new, p, cube.var_mask[cube.output]);
  350.         PUTSIZE(new, SIZE(p));
  351.         SET(new, REDUND);
  352.     }
  353.  
  354.     /* Find ways (sop form) to fail to cover output indexed by n */
  355.     Flist = cube2list(F1, D);
  356.     table = sf_new(10, Rp_size);
  357.     foreach_set(F1, last, p) {
  358.     set_fill(Rp_start, Rp_size);
  359.     set_remove(Rp_start, SIZE(p));
  360.     table = sf_append(table, fcube_is_covered(Flist, p));
  361.     RESET(p, REDUND);
  362.     }
  363.     set_fill(Rp_start, Rp_size);
  364.     foreach_set(table, last, p) {
  365.     set_diff(p, Rp_start, p);
  366.     }
  367.  
  368.     /* complement this to get possible ways to cover the function */
  369.     for(i = 0; i < Rp_size; i++) {
  370.     if (! is_in_set(select, i)) {
  371.         p = set_new(Rp_size);
  372.         set_insert(p, i);
  373.         table = sf_addset(table, p);
  374.         set_free(p);
  375.     }
  376.     }
  377.     f_table = unate_compl(table);
  378.  
  379.     /* what a pain, but we need bitwise complement of this */
  380.     set_fill(Rp_start, Rp_size);
  381.     foreach_set(f_table, last, p) {
  382.     set_diff(p, Rp_start, p);
  383.     }
  384.  
  385.     free_cubelist(Flist);
  386.     sf_free(F1);
  387.     return f_table;
  388. }
  389. #endif
  390.  
  391. /*
  392.  *  Take a PLA (ON-set, OFF-set and DC-set) and create the
  393.  *  "double-phase characteristic function" which is merely a new
  394.  *  function which has twice as many outputs and realizes both the
  395.  *  function and the complement.
  396.  *
  397.  *  The cube structure is assumed to represent the PLA upon entering.
  398.  *  It will be modified to represent the double-phase function upon
  399.  *  exit.
  400.  *
  401.  *  Only the outputs numbered starting with "first_output" are
  402.  *  duplicated in the output part
  403.  */
  404.  
  405. output_phase_setup(PLA, first_output)
  406. INOUT pPLA PLA;
  407. int first_output;
  408. {
  409.     pcover F, R, D;
  410.     pcube mask, mask1, last;
  411.     int first_part, offset;
  412.     bool save;
  413.     register pcube p, pr, pf;
  414.     register int i, last_part;
  415.  
  416.     if (cube.output == -1)
  417.     fatal("output_phase_setup: must have an output");
  418.  
  419.     F = PLA->F;
  420.     D = PLA->D;
  421.     R = PLA->R;
  422.     first_part = cube.first_part[cube.output] + first_output;
  423.     last_part = cube.last_part[cube.output];
  424.     offset = cube.part_size[cube.output] - first_output;
  425.  
  426.     /* Change the output size, setup the cube structure */
  427.     setdown_cube();
  428.     cube.part_size[cube.output] += offset;
  429.     cube_setup();
  430.  
  431.     /* Create a mask to select that part of the cube which isn't changing */
  432.     mask = set_save(cube.fullset);
  433.     for(i = first_part; i < cube.size; i++)
  434.     set_remove(mask, i);
  435.     mask1 = set_save(mask);
  436.     for(i = cube.first_part[cube.output]; i < first_part; i++) {
  437.     set_remove(mask1, i);
  438.     }
  439.  
  440.     PLA->F = new_cover(F->count + R->count);
  441.     PLA->R = new_cover(F->count + R->count);
  442.     PLA->D = new_cover(D->count);
  443.  
  444.     foreach_set(F, last, p) {
  445.     pf = GETSET(PLA->F, (PLA->F)->count++);
  446.     pr = GETSET(PLA->R, (PLA->R)->count++);
  447.     INLINEset_and(pf, mask, p);
  448.     INLINEset_and(pr, mask1, p);
  449.     for(i = first_part; i <= last_part; i++)
  450.         if (is_in_set(p, i))
  451.         set_insert(pf, i);
  452.     save = FALSE;
  453.     for(i = first_part; i <= last_part; i++)
  454.         if (is_in_set(p, i))
  455.         save = TRUE, set_insert(pr, i+offset);
  456.     if (! save) PLA->R->count--;
  457.     }
  458.  
  459.     foreach_set(R, last, p) {
  460.     pf = GETSET(PLA->F, (PLA->F)->count++);
  461.     pr = GETSET(PLA->R, (PLA->R)->count++);
  462.     INLINEset_and(pf, mask1, p);
  463.     INLINEset_and(pr, mask, p);
  464.     save = FALSE;
  465.     for(i = first_part; i <= last_part; i++)
  466.         if (is_in_set(p, i))
  467.         save = TRUE, set_insert(pf, i+offset);
  468.     if (! save) PLA->F->count--;
  469.     for(i = first_part; i <= last_part; i++)
  470.         if (is_in_set(p, i))
  471.         set_insert(pr, i);
  472.     }
  473.  
  474.     foreach_set(D, last, p) {
  475.     pf = GETSET(PLA->D, (PLA->D)->count++);
  476.     INLINEset_and(pf, mask, p);
  477.     for(i = first_part; i <= last_part; i++)
  478.         if (is_in_set(p, i)) {
  479.         set_insert(pf, i);
  480.         set_insert(pf, i+offset);
  481.         }
  482.     }
  483.  
  484.     free_cover(F);
  485.     free_cover(D);
  486.     free_cover(R);
  487.     set_free(mask);
  488.     set_free(mask1);
  489. }
  490.  
  491. /*
  492.  *  set_phase -- given a "cube" which describes which phases of the output
  493.  *  are to be implemented, compute the appropriate on-set and off-set
  494.  */
  495. pPLA set_phase(PLA)
  496. INOUT pPLA PLA;
  497. {
  498.     pcover F1, R1;
  499.     register pcube last, p, outmask;
  500.     register pcube temp=cube.temp[0], phase=PLA->phase, phase1=cube.temp[1];
  501.  
  502.     outmask = cube.var_mask[cube.num_vars - 1];
  503.     set_diff(phase1, outmask, phase);
  504.     set_or(phase1, set_diff(temp, cube.fullset, outmask), phase1);
  505.     F1 = new_cover((PLA->F)->count + (PLA->R)->count);
  506.     R1 = new_cover((PLA->F)->count + (PLA->R)->count);
  507.  
  508.     foreach_set(PLA->F, last, p) {
  509.     if (! setp_disjoint(set_and(temp, p, phase), outmask))
  510.         set_copy(GETSET(F1, F1->count++), temp);
  511.     if (! setp_disjoint(set_and(temp, p, phase1), outmask))
  512.         set_copy(GETSET(R1, R1->count++), temp);
  513.     }
  514.     foreach_set(PLA->R, last, p) {
  515.     if (! setp_disjoint(set_and(temp, p, phase), outmask))
  516.         set_copy(GETSET(R1, R1->count++), temp);
  517.     if (! setp_disjoint(set_and(temp, p, phase1), outmask))
  518.         set_copy(GETSET(F1, F1->count++), temp);
  519.     }
  520.     free_cover(PLA->F);
  521.     free_cover(PLA->R);
  522.     PLA->F = F1;
  523.     PLA->R = R1;
  524.     return PLA;
  525. }
  526.  
  527. #define POW2(x)        (1 << (x))
  528.  
  529. void opoall(PLA, first_output, last_output, opo_strategy)
  530. pPLA PLA;
  531. int first_output, last_output;
  532. int opo_strategy;
  533. {
  534.     pcover F, D, R, best_F, best_D, best_R;
  535.     int i, j, ind, num;
  536.     pcube bestphase;
  537.  
  538.     opo_exact = opo_strategy;
  539.  
  540.     if (PLA->phase != NULL) {
  541.     set_free(PLA->phase);
  542.     }
  543.  
  544.     bestphase = set_save(cube.fullset);
  545.     best_F = sf_save(PLA->F);
  546.     best_D = sf_save(PLA->D);
  547.     best_R = sf_save(PLA->R);
  548.  
  549.     for(i = 0; i < POW2(last_output - first_output + 1); i++) {
  550.  
  551.     /* save the initial PLA covers */
  552.     F = sf_save(PLA->F);
  553.     D = sf_save(PLA->D);
  554.     R = sf_save(PLA->R);
  555.  
  556.     /* compute the phase cube for this iteration */
  557.     PLA->phase = set_save(cube.fullset);
  558.     num = i;
  559.     for(j = last_output; j >= first_output; j--) {
  560.         if (num % 2 == 0) {
  561.         ind = cube.first_part[cube.output] + j;
  562.         set_remove(PLA->phase, ind);
  563.         }
  564.         num /= 2;
  565.     }
  566.  
  567.     /* set the phase and minimize */
  568.     (void) set_phase(PLA);
  569.     printf("# phase is %s\n", pc1(PLA->phase));
  570.     summary = TRUE;
  571.     minimize(PLA);
  572.  
  573.     /* see if this is the best so far */
  574.     if (PLA->F->count < best_F->count) {
  575.         /* save new best solution */
  576.         set_copy(bestphase, PLA->phase);
  577.         sf_free(best_F);
  578.         sf_free(best_D);
  579.         sf_free(best_R);
  580.         best_F = PLA->F;
  581.         best_D = PLA->D;
  582.         best_R = PLA->R;
  583.     } else {
  584.         /* throw away the solution */
  585.         free_cover(PLA->F);
  586.         free_cover(PLA->D);
  587.         free_cover(PLA->R);
  588.     }
  589.     set_free(PLA->phase);
  590.  
  591.     /* restore the initial PLA covers */
  592.     PLA->F = F;
  593.     PLA->D = D;
  594.     PLA->R = R;
  595.     }
  596.  
  597.     /* one more minimization to restore the best answer */
  598.     PLA->phase = bestphase;
  599.     sf_free(PLA->F);
  600.     sf_free(PLA->D);
  601.     sf_free(PLA->R);
  602.     PLA->F = best_F;
  603.     PLA->D = best_D;
  604.     PLA->R = best_R;
  605. }
  606.  
  607. static void minimize(PLA)
  608. pPLA PLA;
  609. {
  610.     if (opo_exact) {
  611.     EXEC_S(PLA->F = minimize_exact(PLA->F,PLA->D,PLA->R,1), "EXACT", PLA->F);
  612.     } else {
  613.     EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), "ESPRESSO  ",PLA->F);
  614.     }
  615. }
  616.